package com.linyaonan.leetcode.easy._1071;

/**
 * 对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
 *
 * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：str1 = "ABCABC", str2 = "ABC"
 * 输出："ABC"
 * 示例 2：
 *
 * 输入：str1 = "ABABAB", str2 = "ABAB"
 * 输出："AB"
 * 示例 3：
 *
 * 输入：str1 = "LEET", str2 = "CODE"
 * 输出：""
 *
 *
 * 提示：
 *
 * 1 <= str1.length, str2.length <= 1000
 * str1 和 str2 由大写英文字母组成
 *
 * @author: Lin
 * @date: 2024/3/6
 */
public class GreatestCommonDivisorOfStrings {

    /**
     * 暴力分析
     *
     * 字符串长度定了后，首先计算可能存在的公约数，然后公约数从大到小进行分析
     *
     * @param str1
     * @param str2
     * @return
     */
    public String gcdOfStrings(String str1, String str2) {
        int l1 = str1.length();
        int l2 = str2.length();
        int min = Math.min(l1, l2);

        for (int i = min; i >=1; i--) {
            // 找到约数
            if (l1 % i == 0 && l2 % i == 0) {
                String ss = str1.substring(0, i);
                if (checkIsDivisor(ss, str1) && checkIsDivisor(ss, str2)) {
                    return ss;
                }
            }
        }
        return "";
    }

    private boolean checkIsDivisor(String ss, String str) {
        int c = str.length() / ss.length();

        for (int i = 0; i < c; i++) {
            for (int j = 0; j < ss.length(); j++) {
                if (ss.charAt(j) != str.charAt(j + ss.length() * i)) {
                    return false;
                }
            }
        }

        return true;
    }

}
